import java.util.ArrayList;
import java.util.Collections;

/*
 * @lc app=leetcode.cn id=556 lang=java
 *
 * [556] 下一个更大元素 III
 */

// @lc code=start
class Solution {
    public int nextGreaterElement(int n) {
        ArrayList<Integer> arr=new ArrayList<Integer>(32);
        while(n>0){
            arr.add(n%10);
            n/=10;
        }
        int i=0;
        while(i==0||arr.get(i-1)<arr.get(i)){
            i++;
            if(i==arr.size()){
                return -1;
            }
        }
        int target=arr.get(i);
        int left=0,right=i-1;
        while(left<right){
            int mid=(left+right)>>1;
            if(arr.get(mid)<target){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        Collections.swap(arr, left, i);
        Collections.reverse(arr);
        int ans=0;
        for(int num:arr){
            ans=ans*10+num;
        }
        return ans;
    }
}
// @lc code=end

